package com.murphy.algorithm.search;

/**
 * 二分查找
 * @author dongsufeng
 * @date 2020/9/22 14:28
 * @version 1.0
 */
public class Bsearch {
	/**
	 * 第一个与查找值相等的值
	 * 设置两个指针分别指向数组收尾
	 * 获取数组中间值，跟value做对比，如果小于中间值说明在中间值左侧，反之在右侧
	 * @param items
	 * @param value 要查找的数
	 * @return
	 */
	public static int lSearch(int [] items,int value){
		//指定指针分别指向数组首位
		int low = 0;
		int high = items.length-1;
		//低位不能大于高位
		while (low <= high){
			//获取中间值:类似于（low+high）/2
			int mid = low + ((high-low) >> 1);
			//如果中间值大于等于value则将最高值设为中间值-1
			//要取第一个相等的，，所以相等的情况还要继续往前查找
			if (items[mid] >= value){
				high = mid-1;
			}else {
				low = mid+1;
			}
		}
		//如果要找第一个大于等于的值：去掉 items[high] == value就可以
		if (low < items.length && items[low] == value){
			return low;
		}
		return -1;
	}

	/**
	 * 查找最后一个相等的下标
	 * @param items
	 * @param value
	 * @return
	 */
	public static int rSearch(int [] items,int value){
		int low = 0;
		int high = items.length-1;
		while (low <= high){
			int mid = low + ((high - low) >> 1);
			//如果小于等于说明在右边，将最小值设为mid+1
			if (items[mid] <= value){
				low = mid + 1;
			}else {
				high = mid - 1;
			}
		}
		//如果要找最后一个小于等于的值：去掉 items[high] == value就可以
		if (high <= items.length && items[high] == value){
			return high;
		}
		return -1;
	}
	public static int search(int [] items,int value){
		int low = 0;
		int high = items.length-1;
		while (low <= high){
			//获取中间值:类似于（low+high）/2
			int mid = low + ((high - low) >> 1);
			if (items[mid] > value){
				high = mid - 1;
			}else if (items[mid] < value){
				low = mid +1;
			}else {
				return mid;
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		int [] items={1,2,3,4,4,4,6,7,8};
		int index = search(items, 5);
		System.out.println(index);
	}
}
